package william.array;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ZhangShenao
 * @date 2024/1/8
 * @description <a href="https://leetcode.cn/problems/two-sum/description/">...</a>
 */
public class Leetcode1_两数之和 {
    public int[] twoSum(int[] nums, int target) {
        //边界条件校验
        if (nums == null || nums.length < 2) {
            return new int[]{};
        }

        //使用一个HashMap保存中间计算结果,可以减少一轮对数组的遍历
        //key=数组元素 value=元素所在下标
        Map<Integer, Integer> cache = new HashMap<>(nums.length);

        //遍历数组
        for (int i = 0; i < nums.length; i++) {
            //在中间结果中,查找目标和与当前元素的差值
            int num = nums[i];
            int remain = target - num;
            if (cache.containsKey(remain)) { //找到目标元素,直接返回所在下标
                return new int[]{cache.get(remain), i};
            }

            //未找到目标元素,则将当前元素及所在下标保存到中间结果中,继续遍历
            cache.put(num, i);
        }

        //未找到目标元素
        return new int[]{};
    }
}
